/**
 * Definition for Node.
 * class Node {
 *     val: number
 *     next: Node | null
 *     random: Node | null
 *     constructor(val?: number, next?: Node, random?: Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *         this.random = (random===undefined ? null : random)
 *     }
 * }
 */

function copyRandomList(head: Node | null): Node | null {
    const dummyNode = new Node();
    let ans = dummyNode;
    let cur = head;
    const hash = new Map();
    while (cur) {
        //? 先弄next
        ans.next = new Node(cur.val);
        ans = ans.next;
        //? 哈希表保存新旧节点（key旧value新）的对应关系 这步是找到random指向的关键
        hash.set(cur, ans);
        cur = cur.next;
    }
    hash.forEach((v, k) => {
        //? 直接找到旧节点的random指向的旧节点对应的新节点
        v.random = hash.get(k.random) || null;
    });
    return dummyNode.next;

};
